/*-- Maze.cpp -------------------------------------------------------*/
#include <cassert>
#include <stdlib.h>
#include <ctime>
#include "Maze.h"

#define random(x) (rand()%(x))

using namespace std;

#define SPACE       0   // 0，通路或空格
#define BLOCK       1   // 1，障碍或围墙
#define NORTH       2   // 2，北
#define ENTRANCE    3   // 3，入口
#define WEST        4   // 4，西
#define EXITPORT    5   // 5，出口
#define EAST        6   // 6，东
#define DEADEND     7   // 7，死胡同
#define SOUTH       8   // 8，南
#define SOUTHEAST   9   // 9，东南
#define SOUTHWEST   10  // 10，西南
#define NORTHWEST   11  // 11，西北
#define NORTHEAST   12  // 12，东北

string p[] =
{
    "  ",   // 0，通路
    "■",   // 1，障碍或围墙
    "↑",   // 2，北
    "○",   // 3，入口
    "←",   // 4，西
    "★",   // 5，出口
    "→",   // 6，东
    "",   // 7，死胡同
    "↓",   // 8，南
    "↘",   // 9，东南
    "↙",   // 10，西南
    "↖",   // 11，西北
    "↗"   // 12，东北
};  // 用于打印迷宫


Maze::Maze()
{
    //ctor
}

void Maze::init()
{
    cout << "Size of maze: ";
    cin >> r >> c;

    assert(r > 0 && c > 0);

    /*---------- 分配数组------------*/
    m = new int*[r + 2];

    for (int i = 0; i < r + 2 ; i++ )
        m[i] = new int[c + 2];

    /*---------- “画” 围墙 --------------------------------
        障碍或围墙用 1 表示，通路用 0 表示
     ----------------------------------------------------*/
    for (int i = 0; i < r + 2 ; i++)
    {
        m[i][0] = BLOCK;
        m[i][c + 1] = BLOCK;
    }

    for (int i = 0; i < c + 2 ; i++)
    {
        m[0][i] = BLOCK;
        m[r + 1][i] = BLOCK;
    }

    /*---------- 输入迷宫数据------------*/
    bool autoMaze = false;      // 自动生成迷宫
    cout << "Auto maze?(0/1) ";
    cin >> autoMaze;

    if (autoMaze)
    {
        for (int i = 1; i < r + 1 ; i++ )
        {
            for (int j = 1; j < c + 1 ; j++ )
            {
                srand((int)time(0) + i * j * 2);

                if (random(20) > 4) m[i][j] = SPACE;
                else m[i][j] = BLOCK;
            }
        }

        display();
    }
    else
    {
        for (int i = 1; i < r + 1 ; i++ )
        {
            cout << "row " << i << ": ";

            for (int j = 1; j < c + 1 ; j++ )
                cin >> m[i][j];
        }
    }

    /*---------- 设置迷宫入口和出口 ------------*/
    int tempR, tempC;
    cout << "ENTRANCE: ";
    cin >> tempR >> tempC;
    assert((tempR == 1 || tempR == r || tempC == 1 || tempC == c) &&
           (tempR > 0 && tempR <= r && tempC > 0 && tempC <= c));
    m[tempR][tempC] = ENTRANCE; // 入口用 3 表示
    entra.r = tempR;
    entra.c = tempC;

    cout << "EXIT: ";
    cin >> tempR >> tempC;
    assert((tempR == 1 || tempR == r || tempC == 1 || tempC == c) &&
           (tempR > 0 && tempR <= r && tempC > 0 && tempC <= c));
    m[tempR][tempC] = EXITPORT; // 出口用 5 表示
    exi.r = tempR;
    exi.c = tempC;

    assert(entra.r != exi.r || entra.c != exi.c);   // 限定入口与出口不可相同
}

void Maze::display() const
{
    for (int i = 0; i < r + 2 ; i++ )
    {
        for (int j = 0; j < c + 2 ; j++ )
            cout << p[m[i][j]];

        cout << "\n";
    }

    cout << "\n";
}

void Maze::getPath()
{
    if (!s.empty())
        s.clear();

    PosType curPos = entra;
    int step = 0;
    bool found = false;
    s.push(ElemType(step, curPos.r, curPos.c, ENTRANCE)); // 首先将入口压栈

    ElemType tempElem;

    bool viewEachStep = false;
    cout << "View each step?(0/1) ";
    cin >> viewEachStep;

    do
    {
        if (viewEachStep)
        {
            system("pause");
            cout << "---------- step " << step
                 << " ----------\n";
            display();
        }

        tempElem = getNext(s.top().seat); // 根据栈顶位置找下一个步

        if (m[tempElem.seat.r][tempElem.seat.c] == EXITPORT)
            found = true; // 找到的下一位置是出口
        else
        {
            // 不是出口
            if (tempElem.direction)
            {
                // 有下一步可走
                tempElem.step = ++step;
                s.push(tempElem);   // 将下一步位置压栈
            }
            else
            {
                // 找不到下一位置
                step--;

                if (s.top().direction != ENTRANCE)
                    m[s.top().seat.r][s.top().seat.c] = DEADEND; // 当前栈顶是死胡同

                s.pop();    // 在路径中删除当前位置
            }
        }
    }
    while (!s.empty() && !found);

    /** ---------- 输出结果 ----------- **/
    if (found)
    {
        cout << "\n--------------- got path ----------------" << endl;

        for (; !s.empty() ; s.pop())
            cout << "step " << s.top().step << ": " << p[s.top().direction] << endl;
    }
    else
        cout << "\n--------------- no path ----------------" << endl;

}

ElemType Maze::getNext(const PosType curPos)
{
    int tempR = curPos.r;
    int tempC = curPos.c;
    int exitR = exi.r;
    int exitC = exi.c;
    ElemType tempElem = ElemType(1, 0, 0, SPACE);

    if (tempR<= exitR && tempC<=exitC)
    {
        // 在出口左上角
        getNextNW(tempElem, tempR, tempC);
        return tempElem;
    }

    if (tempR<= exitR && tempC>=exitC)
    {
        // 在出口右上角
        getNextNE(tempElem, tempR, tempC);
        return tempElem;
    }

    if (tempR>= exitR && tempC<=exitC)
    {
        // 在出口左下角
        getNextSW(tempElem, tempR, tempC);
        return tempElem;
    }

    if (tempR>= exitR && tempC>=exitC)
    {
        // 在出口右下角
        getNextSE(tempElem, tempR, tempC);
        return tempElem;
    }

    return tempElem;
}

void Maze::getNextNW(ElemType &tempElem, int tempR, int tempC)
{
    // 西北 11
    if (!(m[tempR][tempC + 1] * m[tempR + 1][tempC] + m[tempR + 1][tempC + 1]) || m[tempR + 1][tempC + 1] == EXITPORT)
    {
        // 东南 // 逻辑计算 ((!a || !b) && !c) || d == !(a * b + c) || d
        if (m[tempR + 1][tempC + 1] != EXITPORT)
        {
            m[tempR + 1][tempC + 1] = SOUTHEAST;
        }

        tempElem.seat.r = tempR + 1;
        tempElem.seat.c = tempC + 1;
        tempElem.direction = m[tempR + 1][tempC + 1];

        return;
    }

    if (m[tempR + 1][tempC] == SPACE || m[tempR + 1][tempC] == EXITPORT)
    {
        // 南
        if (m[tempR + 1][tempC] != EXITPORT)
        {
            m[tempR + 1][tempC] = SOUTH;
        }

        tempElem.seat.r = tempR + 1;
        tempElem.seat.c = tempC;
        tempElem.direction = m[tempR + 1][tempC];

        return;
    }

    if (m[tempR][tempC + 1] == SPACE || m[tempR][tempC + 1] == EXITPORT)
    {
        // 东
        if (m[tempR][tempC + 1] != EXITPORT)
        {
            m[tempR][tempC + 1] = EAST;
        }

        tempElem.seat.r = tempR;
        tempElem.seat.c = tempC + 1;
        tempElem.direction = m[tempR][tempC + 1];

        return;
    }

    if (!(m[tempR][tempC - 1] * m[tempR + 1][tempC] + m[tempR + 1][tempC - 1]) || m[tempR + 1][tempC - 1] == EXITPORT)
    {
        // 西南
        if (m[tempR + 1][tempC - 1] != EXITPORT)
        {
            m[tempR + 1][tempC - 1] = SOUTHWEST;
        }

        tempElem.seat.r = tempR + 1;
        tempElem.seat.c = tempC - 1;
        tempElem.direction = m[tempR + 1][tempC - 1];

        return;
    }

    if (!(m[tempR][tempC + 1] * m[tempR - 1][tempC] + m[tempR - 1][tempC + 1]) || m[tempR - 1][tempC + 1] == EXITPORT)
    {
        // 东北
        if (m[tempR - 1][tempC + 1] != EXITPORT)
        {
            m[tempR - 1][tempC + 1] = NORTHEAST;
        }

        tempElem.seat.r = tempR - 1;
        tempElem.seat.c = tempC + 1;
        tempElem.direction = m[tempR - 1][tempC + 1];

        return;
    }

    if (m[tempR][tempC - 1] == SPACE || m[tempR][tempC - 1] == EXITPORT)
    {
        // 西
        if (m[tempR][tempC - 1] != EXITPORT)
        {
            m[tempR][tempC - 1] = WEST;
        }

        tempElem.seat.r = tempR;
        tempElem.seat.c = tempC - 1;
        tempElem.direction = m[tempR][tempC - 1];

        return;
    }

    if (m[tempR - 1][tempC] == SPACE || m[tempR - 1][tempC] == EXITPORT)
    {
        // 北
        if (m[tempR - 1][tempC] != EXITPORT)
        {
            m[tempR - 1][tempC] = NORTH;
        }

        tempElem.seat.r = tempR - 1;
        tempElem.seat.c = tempC;
        tempElem.direction = m[tempR - 1][tempC];

        return;
    }

    if (!(m[tempR][tempC - 1] * m[tempR - 1][tempC] + m[tempR - 1][tempC - 1]) || m[tempR - 1][tempC - 1] == EXITPORT)
    {
        // 西北
        if (m[tempR - 1][tempC - 1] != EXITPORT)
        {
            m[tempR - 1][tempC - 1] = NORTHWEST;
        }

        tempElem.seat.r = tempR - 1;
        tempElem.seat.c = tempC - 1;
        tempElem.direction = m[tempR - 1][tempC - 1];

        return;
    }
}

void Maze::getNextNE(ElemType &tempElem, int tempR, int tempC)
{
    // 东北 12
    if (!(m[tempR][tempC - 1] * m[tempR + 1][tempC] + m[tempR + 1][tempC - 1]) || m[tempR + 1][tempC - 1] == EXITPORT)
    {
        // 西南
        if (m[tempR + 1][tempC - 1] != EXITPORT)
        {
            m[tempR + 1][tempC - 1] = SOUTHWEST;
        }

        tempElem.seat.r = tempR + 1;
        tempElem.seat.c = tempC - 1;
        tempElem.direction = m[tempR + 1][tempC - 1];

        return;
    }

    if (m[tempR][tempC - 1] == SPACE || m[tempR][tempC - 1] == EXITPORT)
    {
        // 西
        if (m[tempR][tempC - 1] != EXITPORT)
        {
            m[tempR][tempC - 1] = WEST;
        }

        tempElem.seat.r = tempR;
        tempElem.seat.c = tempC - 1;
        tempElem.direction = m[tempR][tempC - 1];

        return;
    }

    if (m[tempR + 1][tempC] == SPACE || m[tempR + 1][tempC] == EXITPORT)
    {
        // 南
        if (m[tempR + 1][tempC] != EXITPORT)
        {
            m[tempR + 1][tempC] = SOUTH;
        }

        tempElem.seat.r = tempR + 1;
        tempElem.seat.c = tempC;
        tempElem.direction = m[tempR + 1][tempC];

        return;
    }

    if (!(m[tempR][tempC + 1] * m[tempR + 1][tempC] + m[tempR + 1][tempC + 1]) || m[tempR + 1][tempC + 1] == EXITPORT)
    {
        // 东南 // 逻辑计算 ((!a || !b) && !c) || d == !(a * b + c) || d
        if (m[tempR + 1][tempC + 1] != EXITPORT)
        {
            m[tempR + 1][tempC + 1] = SOUTHEAST;
        }

        tempElem.seat.r = tempR + 1;
        tempElem.seat.c = tempC + 1;
        tempElem.direction = m[tempR + 1][tempC + 1];

        return;
    }

    if (!(m[tempR][tempC - 1] * m[tempR - 1][tempC] + m[tempR - 1][tempC - 1]) || m[tempR - 1][tempC - 1] == EXITPORT)
    {
        // 西北
        if (m[tempR - 1][tempC - 1] != EXITPORT)
        {
            m[tempR - 1][tempC - 1] = NORTHWEST;
        }

        tempElem.seat.r = tempR - 1;
        tempElem.seat.c = tempC - 1;
        tempElem.direction = m[tempR - 1][tempC - 1];

        return;
    }

    if (m[tempR - 1][tempC] == SPACE || m[tempR - 1][tempC] == EXITPORT)
    {
        // 北
        if (m[tempR - 1][tempC] != EXITPORT)
        {
            m[tempR - 1][tempC] = NORTH;
        }

        tempElem.seat.r = tempR - 1;
        tempElem.seat.c = tempC;
        tempElem.direction = m[tempR - 1][tempC];

        return;
    }

    if (m[tempR][tempC + 1] == SPACE || m[tempR][tempC + 1] == EXITPORT)
    {
        // 东
        if (m[tempR][tempC + 1] != EXITPORT)
        {
            m[tempR][tempC + 1] = EAST;
        }

        tempElem.seat.r = tempR;
        tempElem.seat.c = tempC + 1;
        tempElem.direction = m[tempR][tempC + 1];

        return;
    }

    if (!(m[tempR][tempC + 1] * m[tempR - 1][tempC] + m[tempR - 1][tempC + 1]) || m[tempR - 1][tempC + 1] == EXITPORT)
    {
        // 东北
        if (m[tempR - 1][tempC + 1] != EXITPORT)
        {
            m[tempR - 1][tempC + 1] = NORTHEAST;
        }

        tempElem.seat.r = tempR - 1;
        tempElem.seat.c = tempC + 1;
        tempElem.direction = m[tempR - 1][tempC + 1];

        return;
    }
}

void Maze::getNextSW(ElemType &tempElem, int tempR, int tempC)
{
    // 西南 10

    if (!(m[tempR][tempC + 1] * m[tempR - 1][tempC] + m[tempR - 1][tempC + 1]) || m[tempR - 1][tempC + 1] == EXITPORT)
    {
        // 东北
        if (m[tempR - 1][tempC + 1] != EXITPORT)
        {
            m[tempR - 1][tempC + 1] = NORTHEAST;
        }

        tempElem.seat.r = tempR - 1;
        tempElem.seat.c = tempC + 1;
        tempElem.direction = m[tempR - 1][tempC + 1];

        return;
    }

    if (m[tempR - 1][tempC] == SPACE || m[tempR - 1][tempC] == EXITPORT)
    {
        // 北
        if (m[tempR - 1][tempC] != EXITPORT)
        {
            m[tempR - 1][tempC] = NORTH;
        }

        tempElem.seat.r = tempR - 1;
        tempElem.seat.c = tempC;
        tempElem.direction = m[tempR - 1][tempC];

        return;
    }

    if (m[tempR][tempC + 1] == SPACE || m[tempR][tempC + 1] == EXITPORT)
    {
        // 东
        if (m[tempR][tempC + 1] != EXITPORT)
        {
            m[tempR][tempC + 1] = EAST;
        }

        tempElem.seat.r = tempR;
        tempElem.seat.c = tempC + 1;
        tempElem.direction = m[tempR][tempC + 1];

        return;
    }

    if (!(m[tempR][tempC - 1] * m[tempR - 1][tempC] + m[tempR - 1][tempC - 1]) || m[tempR - 1][tempC - 1] == EXITPORT)
    {
        // 西北
        if (m[tempR - 1][tempC - 1] != EXITPORT)
        {
            m[tempR - 1][tempC - 1] = NORTHWEST;
        }

        tempElem.seat.r = tempR - 1;
        tempElem.seat.c = tempC - 1;
        tempElem.direction = m[tempR - 1][tempC - 1];

        return;
    }

    if (!(m[tempR][tempC + 1] * m[tempR + 1][tempC] + m[tempR + 1][tempC + 1]) || m[tempR + 1][tempC + 1] == EXITPORT)
    {
        // 东南 // 逻辑计算 ((!a || !b) && !c) || d == !(a * b + c) || d
        if (m[tempR + 1][tempC + 1] != EXITPORT)
        {
            m[tempR + 1][tempC + 1] = SOUTHEAST;
        }

        tempElem.seat.r = tempR + 1;
        tempElem.seat.c = tempC + 1;
        tempElem.direction = m[tempR + 1][tempC + 1];

        return;
    }

    if (m[tempR + 1][tempC] == SPACE || m[tempR + 1][tempC] == EXITPORT)
    {
        // 南
        if (m[tempR + 1][tempC] != EXITPORT)
        {
            m[tempR + 1][tempC] = SOUTH;
        }

        tempElem.seat.r = tempR + 1;
        tempElem.seat.c = tempC;
        tempElem.direction = m[tempR + 1][tempC];

        return;
    }

    if (m[tempR][tempC - 1] == SPACE || m[tempR][tempC - 1] == EXITPORT)
    {
        // 西
        if (m[tempR][tempC - 1] != EXITPORT)
        {
            m[tempR][tempC - 1] = WEST;
        }

        tempElem.seat.r = tempR;
        tempElem.seat.c = tempC - 1;
        tempElem.direction = m[tempR][tempC - 1];

        return;
    }

    if (!(m[tempR][tempC - 1] * m[tempR + 1][tempC] + m[tempR + 1][tempC - 1]) || m[tempR + 1][tempC - 1] == EXITPORT)
    {
        // 西南
        if (m[tempR + 1][tempC - 1] != EXITPORT)
        {
            m[tempR + 1][tempC - 1] = SOUTHWEST;
        }

        tempElem.seat.r = tempR + 1;
        tempElem.seat.c = tempC - 1;
        tempElem.direction = m[tempR + 1][tempC - 1];

        return;
    }
}

void Maze::getNextSE(ElemType &tempElem, int tempR, int tempC)
{
    // 东南 9

    if (!(m[tempR][tempC - 1] * m[tempR - 1][tempC] + m[tempR - 1][tempC - 1]) || m[tempR - 1][tempC - 1] == EXITPORT)
    {
        // 西北
        if (m[tempR - 1][tempC - 1] != EXITPORT)
        {
            m[tempR - 1][tempC - 1] = NORTHWEST;
        }

        tempElem.seat.r = tempR - 1;
        tempElem.seat.c = tempC - 1;
        tempElem.direction = m[tempR - 1][tempC - 1];

        return;
    }

    if (m[tempR - 1][tempC] == SPACE || m[tempR - 1][tempC] == EXITPORT)
    {
        // 北
        if (m[tempR - 1][tempC] != EXITPORT)
        {
            m[tempR - 1][tempC] = NORTH;
        }

        tempElem.seat.r = tempR - 1;
        tempElem.seat.c = tempC;
        tempElem.direction = m[tempR - 1][tempC];

        return;
    }

    if (m[tempR][tempC - 1] == SPACE || m[tempR][tempC - 1] == EXITPORT)
    {
        // 西
        if (m[tempR][tempC - 1] != EXITPORT)
        {
            m[tempR][tempC - 1] = WEST;
        }

        tempElem.seat.r = tempR;
        tempElem.seat.c = tempC - 1;
        tempElem.direction = m[tempR][tempC - 1];

        return;
    }

    if (!(m[tempR][tempC + 1] * m[tempR - 1][tempC] + m[tempR - 1][tempC + 1]) || m[tempR - 1][tempC + 1] == EXITPORT)
    {
        // 东北
        if (m[tempR - 1][tempC + 1] != EXITPORT)
        {
            m[tempR - 1][tempC + 1] = NORTHEAST;
        }

        tempElem.seat.r = tempR - 1;
        tempElem.seat.c = tempC + 1;
        tempElem.direction = m[tempR - 1][tempC + 1];

        return;
    }

    if (!(m[tempR][tempC - 1] * m[tempR + 1][tempC] + m[tempR + 1][tempC - 1]) || m[tempR + 1][tempC - 1] == EXITPORT)
    {
        // 西南
        if (m[tempR + 1][tempC - 1] != EXITPORT)
        {
            m[tempR + 1][tempC - 1] = SOUTHWEST;
        }

        tempElem.seat.r = tempR + 1;
        tempElem.seat.c = tempC - 1;
        tempElem.direction = m[tempR + 1][tempC - 1];

        return;
    }

    if (m[tempR + 1][tempC] == SPACE || m[tempR + 1][tempC] == EXITPORT)
    {
        // 南
        if (m[tempR + 1][tempC] != EXITPORT)
        {
            m[tempR + 1][tempC] = SOUTH;
        }

        tempElem.seat.r = tempR + 1;
        tempElem.seat.c = tempC;
        tempElem.direction = m[tempR + 1][tempC];

        return;
    }

    if (m[tempR][tempC + 1] == SPACE || m[tempR][tempC + 1] == EXITPORT)
    {
        // 东
        if (m[tempR][tempC + 1] != EXITPORT)
        {
            m[tempR][tempC + 1] = EAST;
        }

        tempElem.seat.r = tempR;
        tempElem.seat.c = tempC + 1;
        tempElem.direction = m[tempR][tempC + 1];

        return;
    }

    if (!(m[tempR][tempC + 1] * m[tempR + 1][tempC] + m[tempR + 1][tempC + 1]) || m[tempR + 1][tempC + 1] == EXITPORT)
    {
        // 东南 // 逻辑计算 ((!a || !b) && !c) || d == !(a * b + c) || d
        if (m[tempR + 1][tempC + 1] != EXITPORT)
        {
            m[tempR + 1][tempC + 1] = SOUTHEAST;
        }

        tempElem.seat.r = tempR + 1;
        tempElem.seat.c = tempC + 1;
        tempElem.direction = m[tempR + 1][tempC + 1];

        return;
    }
}

bool Maze::pass(PosType p)
{
    assert(p.r >= 0 && p.c >= 0 && p.r < r + 2 && p.c < c + 2);
    return m[p.r][p.c] == 0;
}

Maze::~Maze()
{
    for (int i = 0; i < r + 2 ; i++)
        delete [] m[i];

    delete m;
}